#include <iostream>
#include <sstream>
#include <fstream>
#include <iterator>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <deque>
#include <algorithm>
#include <sys/time.h>
//#include <sys/resource.h>
using namespace std;

typedef unsigned short int usitype;
typedef unsigned int uitype;
typedef short int sitype;
typedef vector<vector<sitype> > sivec;
typedef vector<vector<bool> > bvec;

struct pos{
    usitype row;
    usitype col;
};

typedef deque<pos> posq;

//Class contains the information of each cell: cell number, terminal number and net number
//Allows to keep track of the connections;

class cell{

    public:

        usitype cellID;
        usitype netNum[4];
        usitype cellPos[2];
        uitype cellCost;
        bool xMirror;
        bool yMirror;
        usitype col;

        cell *terminal[4];

        cell(){
            cellPos[0] =-1;
            cellPos[1]=-1;
            cellCost =0;
            cellID =0;
            terminal[0]=NULL;
            terminal[1]=NULL;
            terminal[2]=NULL;
            terminal[3]=NULL;
            netNum[0]=0;
            netNum[1]=0;
            netNum[2]=0;
            netNum[3]=0;
        }

 //set the cellID of the cell
        void setCellID(usitype c){
            cellID = c;
        }
//Get the cellID of the cell
        usitype getCellID(){
            return(cellID);
        }

        void setCellPos(usitype col, usitype row){
            cellPos[0]=col;
            cellPos[1]=row;
        }

//Add a new connection to the given terminal
        void addConnection(cell *ci, usitype n, usitype t ){
            netNum[t] = n;
            terminal[t]=ci;

        }

        void xMirrorToggle() {
		xMirror = !xMirror;
        }

        void yMirrorToggle() {
		yMirror = !yMirror;
        }

        usitype getTerminal(usitype n){
            for(usitype i=0;i<4;i++){
                if(netNum[i]==n){
                    return(i+1);
                }
            }
        }

        usitype getCellCost(usitype col,  usitype row){
            int xdist=0; int ydist=0; usitype cost=0;
            for(int i=0;i<4;i++){
                if(netNum[i]!=0){
                        xdist=abs(col-(terminal[i]->cellPos[0]));
                        ydist=abs(row-(terminal[i]->cellPos[1]));
                }
                cost=cost+xdist+ydist;
            }
            return(cost);
        }

        void updateCellCost(){
            cellCost = getCellCost(cellPos[0],cellPos[1]);
        }


};



class cellGrid{
    private:
        usitype rowrand1,colrand1,rowrand2,colrand2;
        usitype rowS,colS,rowT,colT;
        uitype initCost;
        pos source, target;
        posq posStack1,posStack2;
        sivec tmpGrid;
        bool tmpvals,tmpvalt;


    public:
        sivec grid,metal1,metal2;
        bvec freeGrid,expMetal1,expMetal2;
        vector<cell> cellList;
        usitype gridLength;
        int totalCost;
        ofstream ff;

        cellGrid(char* fileName){
            usitype lineNum=0;
            usitype cNum, nNum;
            string line;
            ifstream inFile(fileName,ios_base::in);
            if(inFile.is_open()){
                while (inFile.good()) { 					//if file is good
                    if (lineNum == 0) {						//get the number of cells

                        getline (inFile,line);
                        cNum = atoi(line.c_str());
                        cellList.resize(cNum);

                        for(usitype i=0;i<cellList.size();i++){
                            cellList[i].setCellID(i+1);
                        }

                        gridLength = (usitype)sqrt((double)cNum);
                        double temp = sqrt((double)cNum);
                        if(gridLength != temp) {
                            gridLength++;
                        }
                        grid.resize(gridLength,vector<sitype>(gridLength,-1));
                        tmpGrid.resize(gridLength,vector<sitype>(gridLength,-1));//added
                        cout<<"gridlength: "<<gridLength<<endl;
                        lineNum++;
                        cout<<"Stage1:Successful:No of cells:"<<cNum<<" vect size"<<cellList.size()<<endl;
                    }

                    else if (lineNum == 1) {						//get the number of nets
                        getline(inFile,line);
                        nNum = atoi(line.c_str());
                        lineNum++;
                        cout<<"stage2:Successful:No of Nets: "<<nNum<<" lineNum:"<<lineNum<<endl;
                    }

                    else if (lineNum == 2) {					//get the net connections
                        usitype tmp[5];
                        while (getline(inFile,line)){
                            istringstream iss(line,istringstream::in);
                            istream_iterator<int> it(iss);
                            istream_iterator<int> EOS;
                            int i=0;
                            for(;it!=EOS;it++){
                                tmp[i]=*it;
                                i++;
                            }

                                cellList[tmp[1]-1].addConnection(&cellList[tmp[3]-1],tmp[0],tmp[2]-1);
                                cellList[tmp[3]-1].addConnection(&cellList[tmp[1]-1],tmp[0],tmp[4]-1);

                        }
                        cout<<"Stage3: Successful"<<endl;
                    }
                }
                inFile.close();
            }
            else {
                cerr<<"Error: File \""<<fileName<<"\" cannot be opened.\nPlease check the file name that you have entered"<<endl;
            }

            ff.open("netl.txt");
            ///print cellList
            ff<<" size of cell list:"<<cellList.size()<<endl;
            for(int i=0;i<cellList.size();i++){
                ff<<cellList[i].cellID<<"\t";
                for(int j=0;j<4;j++){
                    if(cellList[i].netNum[j]!=0){
                        ff<<cellList[i].netNum[j]<<","<<j+1<<";"<<cellList[i].terminal[j]->getCellID()<<","<<cellList[i].terminal[j]->getTerminal(cellList[i].netNum[j])<<" ";
                    }
                }

                ff<<endl;
            }
        }

        void createInitPlacement(){

            usitype rowIndex,colIndex;
            usitype n=0;
            vector<vector<usitype> >::iterator it;

            while(n<cellList.size()){
                rowIndex = rand()%gridLength;
                colIndex = rand()%gridLength;
                if(grid[rowIndex][colIndex] == -1){         //interchanging x and y for more randomness!
                    grid[rowIndex][colIndex] = n+1;
                    cellList[n].setCellPos(colIndex,rowIndex);
                    n++;
                }
            }
//Printing!!!!
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    cout<<grid[i][j]<<" ";
                }
                cout<<endl;
            }
            totalCost=getTotalCost();
            initCost=totalCost;

        }

        uitype getTotalCost(){
            uitype totalCost=0;
            for(int i=0;i<cellList.size();i++){
                cellList[i].cellCost=cellList[i].getCellCost(cellList[i].cellPos[0],cellList[i].cellPos[1]);
                totalCost+=cellList[i].cellCost;

            }
            //cout<<"Initial cost:"<<totalCost<<endl;
            return(totalCost);
        }

        void perterb(){

            rowrand1 = rand()%(gridLength);
            colrand1 = rand()%(gridLength);
            rowrand2 = rand()%(gridLength);
            colrand2 = rand()%(gridLength);
        }
        void updateTotalCost(){

            totalCost=totalCost+(getGain());
        }

        int getGain(){
            usitype newCost=0;
            usitype oldCost=0;
            int costdiff=0;
            if(grid[rowrand1][colrand1] >0){
                newCost=cellList[(grid[rowrand1][colrand1]-1)].getCellCost(colrand2,rowrand2);
                oldCost = cellList[grid[rowrand1][colrand1]-1].cellCost;
                //for(int i=0;i<4;i++){
                    //if(cellList[(grid[rowrand1][colrand1]-1)].netNum[i] != 0){
                           //newCost+=2*(abs(colrand1-colrand2)+abs(rowrand1-rowrand2));
                    //}
                //}
            }
            if(grid[rowrand2][colrand2] >0){
                newCost+=cellList[grid[rowrand2][colrand2]-1].getCellCost(colrand1,rowrand1);
                oldCost+= cellList[grid[rowrand2][colrand2]-1].cellCost;

            }


            costdiff = 2*(newCost-oldCost);
            return(costdiff);


        }

        double random(){
            return(rand()/((double)RAND_MAX + 1));
        }

        void accept(){
            updateTotalCost();
            if(grid[rowrand1][colrand1] >0){
                cellList[(grid[rowrand1][colrand1]-1)].setCellPos(colrand2,rowrand2);
                cellList[(grid[rowrand1][colrand1]-1)].updateCellCost();
            }
            if(grid[rowrand2][colrand2] >0){
                cellList[(grid[rowrand2][colrand2]-1)].setCellPos(colrand1,rowrand1);
                cellList[(grid[rowrand2][colrand2]-1)].updateCellCost();
            }
            int temp=grid[rowrand1][colrand1];
            grid[rowrand1][colrand1]=grid[rowrand2][colrand2];
            grid[rowrand2][colrand2]=temp;

        }

        void assignVec(sivec &tmpGrid,sivec &grid){
            for(int i=0;i<tmpGrid.size();i++){
                for(int j=0;j<tmpGrid[i].size();j++){
                    tmpGrid[i][j]=grid[i][j];
                }
            }
        }

        void Metropolis(double T, double M){
            uitype tmp,cost=initCost;
            while (M>0){
                perterb();

                double delH = (double)getGain();
                double randomProb = random();
                double con = exp((double)(-delH)/(T));
                if ((delH<0) || (randomProb < con)){
                    accept();
                    tmp=getTotalCost();
                    if(tmp<cost){
                        cost=tmp;
                        assignVec(tmpGrid,grid);
                    }
                }
                M=M-1;
            }
            cout<<"total cost:"<<cost;
            //cout<<"swap count"<<swapcout<<endl;
        }

        void SA(){
            double T=40, M=45, beta=2,maxTime=4000000, Time=0;//changed time
            //double T=40, M=45, beta=4,maxTime=4000000, Time=0;
            int n;
            while(Time<maxTime){
                    Metropolis(T,M);
                    Time=Time+M;
                    T=0.76*T;  //alpha
                    M=beta*M;
                    cout<<"T:"<<T<<endl;

            }

            int t=0;
            for(int i=0;i<cellList.size();i++){
                cellList[i].cellCost=cellList[i].getCellCost(cellList[i].cellPos[0],cellList[i].cellPos[1]);
                t+=cellList[i].cellCost;

            }
            cout<<"Actual t:"<<t<<endl;
//Printing!!!!
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    ff<<grid[i][j]<<" ";
                }
                ff<<endl;
            }
            ff.close();

        }

        void updateCellList(){
            assignVec(grid,tmpGrid);
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    if(grid[i][j]>0){
                        cellList[grid[i][j]-1].setCellPos(j,i);
                    }
                }
            }
        }
//////////////////////////////////////////ROUTING//////////////////////////////////////////////////////////////////


        usitype grid_length(){
            usitype a=4,b=2;
            //usitype length=gridLength*4+2;
            usitype length=gridLength*a+b;
            return(length);
        }

        void expandGrid(){
            usitype c=4;
            usitype length=grid_length();
            usitype explength=(7+c*2)*gridLength+9;
            metal1.resize(length,vector<sitype>(length,-2));
            metal2.resize(length,vector<sitype>(length,-2));
            freeGrid.resize(length,vector<bool>(length,0));
            expMetal1.resize(explength,vector<bool>(explength,0));

        }

        void fillGrid(){
            usitype row,col,a=4,b=2;
            expandGrid();
            //updateCellList();
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    if(grid[i][j]>0){
                        //row=4*i+2;col=4*j+2;
                        row=a*i+b;col=a*j+b;
                        metal1[row][col]=-1;//blocked!
                        metal2[row][col]=-1;

                        //freeGrid[4*i+2][4*j+2]=1;

                        metal1[row+1][col]=-1;
                        metal2[row+1][col]=-1;
                        //freeGrid[4*i+3][4*j+2]=1;

                        metal1[row][col+1]=-1;
                        metal2[row][col+1]=-1;
                        //freeGrid[4*i+2][4*j+3]=1;

                        metal1[row+1][col+1]=-1;
                        metal2[row+1][col+1]=-1;
                        //freeGrid[4*i+3][4*j+3]=1;
                        metal1[row+2][col]=-4;
                        metal1[row-1][col]=-4;
                        metal2[row+2][col+1]=-4;
                        metal2[row-1][col+1]=-4;
                    }

                }
            }

//            //Printing!!!!
//            for(int i=0;i<metal1.size();i++){
//                for(int j=0;j<metal1[i].size();j++){
//                    cout<<metal1[i][j]<<" ";
//                }
//                cout<<endl;
//            }
        }

        void initFG(bvec &freeGrid){
            for(int i=0;i<freeGrid.size();i++){
                for(int j=0;j<freeGrid[i].size();j++){
                    freeGrid[i][j]=0;
                   if((metal1[i][j]==-1 || metal1[i][j]==-4 ) && (metal2[i][j]==-1 || metal2[i][j]==-4) ){
                        freeGrid[i][j]=1;
                   }

                }
            }
        }

        bool findST(int i,int j,sivec &metal1, sivec &metal2, bvec &freeGrid){
            usitype a=4,b=2;
            tmpvals=0;tmpvalt=0;
            initFG(freeGrid);

            if(cellList[i].netNum[j]!=0){
                //cout<<"source:"<<cellList[0].cellID<<" terminal:"<<j;
                //cout<<" gx:"<<cellList[0].cellPos[1]<<" gy:"<<cellList[0].cellPos[0]<<" egx:"<<4*cellList[0].cellPos[1]+4<<" egy:"<<4*cellList[0].cellPos[0]+4<<endl;
                if(j==0) {
                    source.row=(a*cellList[i].cellPos[1]+b)-1;
                    source.col=(a*cellList[i].cellPos[0]+b);
                    if(metal1[source.row][source.col]!=-1){
                        metal1[source.row][source.col]=0;
                    }
//                    if(metal2[source.row][source.col]!=-1){
//                        metal2[source.row][source.col]=0;
//                    }
//                    if(freeGrid[source.row][source.col+1]!=1){
//                        freeGrid[source.row][source.col+1]=1;
//                        tmpvals=1;
//                    }


                    //else{return(false);}
                }
                else if(j==1) {
                    source.row= (a*cellList[i].cellPos[1]+b)-1;
                    source.col=(a*cellList[i].cellPos[0]+b)+1;
//                    if(metal1[source.row][source.col]!=-1){
//                        metal1[source.row][source.col]=0;
//                    }
                    if(metal2[source.row][source.col]!=-1){
                        metal2[source.row][source.col]=0;
                    }
//                    if(freeGrid[source.row][source.col-1]!=1){
//                        freeGrid[source.row][source.col-1]=1;
//                        tmpvals=1;
//                    }

                    //else{return(false);}
                }
                else if(j==2) {
                    source.row=(a*cellList[i].cellPos[1]+b)+2;
                    source.col=(a*cellList[i].cellPos[0]+b);
                    if(metal1[source.row][source.col]!=-1){
                        metal1[source.row][source.col]=0;
                    }
//                    if(metal2[source.row][source.col]!=-1){
//                        metal2[source.row][source.col]=0;
//                    }
//                    if(freeGrid[source.row][source.col+1]!=1){
//                        freeGrid[source.row][source.col+1]=1;
//                        tmpvals=1;
//                    }
                    //else{return(false);}
                }
                else if(j==3) {
                    source.row=(a*cellList[i].cellPos[1]+b)+2;
                    source.col=(a*cellList[i].cellPos[0]+b)+1;
//                    if(metal1[source.row][source.col]!=-1){
//                        metal1[source.row][source.col]=0;
//                    }
                    if(metal2[source.row][source.col]!=-1){
                        metal2[source.row][source.col]=0;
                    }
//                    if(freeGrid[source.row][source.col-1]!=1){
//                        freeGrid[source.row][source.col-1]=1;
//                        tmpvals=1;
//                    }
                    //else{return(false);}
                }

                for (int k=0;k<4;k++){
                    if(cellList[i].netNum[j] == cellList[i].terminal[j]->netNum[k]){
                        //cout<<" target:"<<cellList[i].terminal[j]->cellID<<" terminal:"<<k;
                        if(k==0) {
                            target.row=(a*cellList[i].terminal[j]->cellPos[1]+b)-1;
                            target.col=(a*cellList[i].terminal[j]->cellPos[0]+b);
//                            if(metal1[target.row][target.col]!=-1){
//                                metal1[target.row][target.col]=-3;
//                            }
                            if(metal2[target.row][target.col]!=-1){
                                metal2[target.row][target.col]=-3;
                            }
//                            if(freeGrid[target.row][target.col+1]!=1){
//                                freeGrid[target.row][target.col+1]=1;
//                                tmpvalt=1;
//                            }
                        }
                        else if(k==1) {
                            target.row=(a*cellList[i].terminal[j]->cellPos[1]+b)-1;
                            target.col=(a*cellList[i].terminal[j]->cellPos[0]+b)+1;
//                            if(metal1[target.row][target.col]!=-1){
//                                metal1[target.row][target.col]=-3;
//                            }
                            if(metal2[target.row][target.col]!=-1){
                                metal2[target.row][target.col]=-3;
                            }
//                            if(freeGrid[target.row][target.col-1]!=1){
//                                freeGrid[target.row][target.col-1]=1;
//                                tmpvalt=1;
//                            }
                        }
                        else if(k==2) {
                            target.row=(a*cellList[i].terminal[j]->cellPos[1]+b)+2;
                            target.col=(a*cellList[i].terminal[j]->cellPos[0]+b);
                            if(metal1[target.row][target.col]!=-1){
                                metal1[target.row][target.col]=-3;
                            }
//                            if(metal2[target.row][target.col]!=-1){
//                                metal2[target.row][target.col]=-3;
//                            }
//                            if(freeGrid[target.row][target.col+1]!=1){
//                                freeGrid[target.row][target.col+1]=1;
//                                tmpvalt=1;
//                            }
                        }
                        else if(k==3) {
                            cout<<"net:"<<cellList[i].netNum[j];
                            cout<<" row:"<<cellList[i].cellPos[1];
                            cout<<" col:"<<cellList[i].cellPos[1];
                            cout<<" pos row:"<<cellList[i].terminal[j]->cellPos[1];
                            cout<<" pos col:"<<cellList[i].terminal[j]->cellPos[0]<<endl;
                            target.row=(a*cellList[i].terminal[j]->cellPos[1]+b)+2;
                            target.col=(a*cellList[i].terminal[j]->cellPos[0]+b)+1;
                            if(metal1[target.row][target.col]!=-1){
                                metal1[target.row][target.col]=-3;
                            }
//                            if(metal2[target.row][target.col]!=-1){
//                                metal2[target.row][target.col]=-3;
//                            }
//                            if(freeGrid[target.row][target.col-1]!=1){
//                                freeGrid[target.row][target.col-1]=1;
//                                tmpvalt=1;
//                            }
                        }

                    }
                }
            }
            //cout<<"s.r:"<<source.row<<" s.c:"<<source.col<<" t.r:"<<target.row<<" t.c:"<<target.col<<endl;
            //posStack.push_front(source);
            return(true);
        }

        bool validateST(sivec &metal1,sivec &metal2,pos source,pos target){

            if(metal1[source.row][source.col]==-1 && metal2[source.row][source.col]==-1){
                return(false);
            }
            else if(metal1[target.row][target.col]==-1 && metal2[target.row][target.col]==-1){
                return(false);
            }
            else {
                //cout<<"Validated"<<endl;
                return(true);
            }
        }

        bool label(pos source,pos target,sivec &metal1, sivec &metal2, bvec &freeGrid, posq &posStack){
            bool found = false;
            bool top_flag= false, bot_flag =false, right_flag=false, left_flag=false;
            usitype length=grid_length();
            deque<usitype> val;
            usitype row,col,value;
            pos tmp;
            val.push_back(0);
            posStack.push_front(source);
            //cout<<"tarf.row:"<<target.row<<" tor.col:"<<target.col<<endl;
            //initFG(freeGrid);
            freeGrid[source.row][source.col]=1;

            //if(metal1[source.row][source.col]!=-1){
                //cout<<"posStack:"<<posStack.size()<<endl;
                //cout<<"source:"<<metal[source.row][source.col]<<endl;
                while(!found && posStack.size()!=0){
                //cout<<"found:"<<found<<endl;
                //cout<<"cond"<<(!top_flag & !bot_flag & !left_flag & !right_flag)<<endl;
                    tmp=posStack.back();
                    posStack.pop_back();
                    //value=val.back();
                    //val.pop_back();
                    row=tmp.row; col=tmp.col;
                    //cout<<posStack.size()<<endl;

                    //if((top_flag & bot_flag & left_flag & right_flag)){
                    //    return(found);
                    //}

                        if((row+1 < length) && (freeGrid[row+1][col]==0)){
                            //cout<<" bot1";
                            if(row+1==target.row && col==target.col){
                                found=true;
                            }
                            else{
                                freeGrid[row+1][col]=1;
                                if(metal1[row+1][col]!=-1 && metal1[row+1][col]!=-4){
                                    metal1[row+1][col]=val.back()+1;
                                }
                                if(metal2[row+1][col]!=-1 && metal2[row+1][col]!=-4){
                                    metal2[row+1][col]=val.back()+1;
                                }
                                tmp.row=row+1;tmp.col=col;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(row==4*gridLength){bot_flag=true;}
                            }
                        }
                        if((row-1 > -1) && (freeGrid[row-1][col]==0)){
                            //cout<<" top1";
                            if(row-1==target.row && col==target.col){
                                found=true;
                            }
                            else {
                                freeGrid[row-1][col]=1;
                                if(metal1[row-1][col]!=-1 && metal1[row-1][col]!=-4){
                                    metal1[row-1][col]= val.back()+1;
                                }
                                if(metal2[row-1][col]!=-1 && metal2[row-1][col]!=-4){
                                    metal2[row-1][col]= val.back()+1;
                                }
                                tmp.row=row-1;tmp.col=col;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(row==1){top_flag=true;}
                            }
                        }
                        if((col-1 > -1) && (freeGrid[row][col-1]==0)){
                            //cout<<" left1";
                            if(row==target.row && col-1==target.col){
                                found=true;
                            }
                            else {
                                freeGrid[row][col-1]=1;
                                if(metal1[row][col-1]!=-1 && metal1[row][col-1]!=-4){
                                    metal1[row][col-1]= val.back()+1;
                                }
                                if(metal2[row][col-1]!=-1 && metal2[row][col-1]!=-4){
                                    metal2[row][col-1]= val.back()+1;
                                }
                                tmp.row=row;tmp.col=col-1;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(col==1){left_flag=true;}
                            }
                        }
                        if((col+1 < length) && (freeGrid[row][col+1]==0)){
                            //cout<<" right1"<<endl;
                            if(row==target.row && col+1==target.col){
                                found=true;
                            }
                            else {
                                freeGrid[row][col+1]=1;
                                if(metal1[row][col+1]!=-1 && metal1[row][col+1]!=-4){
                                    metal1[row][col+1]= val.back()+1;
                                }
                                if(metal2[row][col+1]!=-1 && metal2[row][col+1]!=-4){
                                    metal2[row][col+1]= val.back()+1;
                                }
                                tmp.row=row;tmp.col=col+1;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(col==4*gridLength){right_flag=true;}
                            }
                        }
                        val.pop_back();
                    //}
                }
                posStack.clear();
                val.clear();
                //cout<<"val size:"<<val.capacity()<<endl;
            return(found);
        }

        void retracePath(pos source, pos target, sivec &metal1, sivec &metal2){

            usitype dist;
            usitype row=target.row, col=target.col,exprow,expcol;
            usitype length=grid_length();
//            sitype tmp[4]={0,0,0,0};
//            if(row+1<row+1 < length) { tmp[0]=metal1[row+1][col];}
//            if(row-1 > -1){ tmp[1]=metal1[row-1][col];}
//            if(col-1>-1){ tmp[2]=metal1[row][col-1];}
//            if(col+1 < length){tmp[3]=metal1[row][col+1];}
//            int index=max_element(tmp,tmp+4)-tmp;
//            dist=*max_element(tmp,tmp+4)+1;

            if(metal1[row][col]==-3 ){//&&(index==2 || index==3)){
                sitype tmp[4]={0,0,0,0};
//                if(row+1<row+1 < length) { tmp[0]=metal1[row+1][col];}
//                if(row-1 > -1){ tmp[1]=metal1[row-1][col];}
                if(col-1>-1){ tmp[2]=metal1[row][col-1];}
                if(col+1 < length){tmp[3]=metal1[row][col+1];}

                dist=*max_element(tmp,tmp+4)+1;
                //cout<<" dist:"<<dist<<endl;
                metal1[row][col]=-1;

                //if()
                //expMetal1[row][col]
                while(row!=source.row || col!=source.col){
                    dist--;

//                    else if(row+1 < length && metal1[row+1][col]==dist){
//                        row=row+1;
//                    }
//                    else if(row-1 > -1 && metal1[row-1][col]==dist){
//                        row=row-1;
//                    }
                    if(col-1>-1 && metal1[row][col-1]==dist){
                        col=col-1;
                    }
                    else if(col+1 < length && metal1[row][col+1]==dist){
                        col=col+1;
                    }
                    else if(metal2[row][col]==dist+1){
                        dist=dist+1;
                        metal2[row][col]=-1;
                        while(row!=source.row || col!=source.col){
                            dist--;

                            if(row+1 < length && metal2[row+1][col]==dist){
                                row=row+1;
                            }
                            else if(row-1 > -1 && metal2[row-1][col]==dist){
                                row=row-1;
                            }
//                            else if(col-1>-1 && metal2[row][col-1]==dist){
//                                col=col-1;
//                            }
//                            else if(col+1 < length && metal2[row][col+1]==dist){
//                                col=col+1;
//                            }

                            else if(metal1[row][col]==dist+1){
                                dist=dist+1;
                                break;
                            }
                            else if(dist==0){
                                row=source.row;
                                col=source.col;
                            }
                            metal2[row][col]=-1;
                        }
                        if(row==source.row && col==source.col)
                        {return;}
                    }
                    else if(dist==0){
                        row=source.row;
                        col=source.col;
                    }
                    metal1[row][col]=-1;
                }
            }
            else if(metal2[row][col]==-3){//} && (index==0 || index ==1)){
                //sitype tmp[]={metal2[row+1][col],metal2[row-1][col],metal2[row][col+1],metal2[row][col-1]};
                //cout<<"yes!"<<endl;
                sitype tmp[4]={0,0,0,0};
                if(row+1<row+1 < length) { tmp[0]=metal2[row+1][col];}
                if(row-1 > -1){ tmp[1]=metal2[row-1][col];}
//                if(col-1>-1){ tmp[2]=metal2[row][col-1];}
//                if(col+1 < length){tmp[3]=metal2[row][col+1];}
                dist=*max_element(tmp,tmp+4)+1;
                //cout<<" dist:"<<dist<<endl;
                metal2[row][col]=-1;
                while(row!=source.row || col!=source.col){
                    dist--;

                    if(row+1 < length && metal2[row+1][col]==dist){
                        row=row+1;
                    }
                    else if(row-1 > -1 && metal2[row-1][col]==dist){
                        row=row-1;
                    }
//                    else if(col-1>-1 && metal2[row][col-1]==dist){
//                        col=col-1;
//                    }
//                    else if(col+1 < length && metal2[row][col+1]==dist){
//                        col=col+1;
//                    }
                    else if(metal1[row][col]==dist+1){
                        //cout<<"dist in m1:"<<dist;
                        dist=dist+1;
                        metal1[row][col]=-1;
                        while(row!=source.row || col!=source.col){
                            dist--;


//                            else if(row+1 < length && metal1[row+1][col]==dist){
//                                row=row+1;
//                            }
//                            else if(row-1 > -1 && metal1[row-1][col]==dist){
//                                row=row-1;
//                            }
                            if(col-1>-1 && metal1[row][col-1]==dist){
                                col=col-1;
                            }
                            else if(col+1 < length && metal1[row][col+1]==dist){
                                col=col+1;
                            }

                            else if(metal2[row][col]==dist+1){
                                dist=dist+1;
                                break;
                            }
                            if (dist==0){
                                row=source.row;
                                col=source.col;
                            }

                            metal1[row][col]=-1;
                        }
                        if(row==source.row && col==source.col)
                        {return;}
                    }
                    else if(dist==0){
                        row=source.row;
                        col=source.col;
                    }
                    metal2[row][col]=-1;
                }
            }
        }

        void updateMetal(int j, pos source, pos target, sivec &metal1, sivec &metal2, bvec &expMetal1,bvec &expMetal2){
            if(j==0){
                //exp
            }
        }



        void clearLabels(sivec &metal,pos source, pos target){
            for(int i=0;i<metal.size();i++){
                for(int j=0;j<metal[i].size();j++){
                    if(metal[i][j]>0){
                        metal[i][j]=-2;
                    }
                }
            }
            if(metal[source.row][source.col]!=-1){
                metal[source.row][source.col]=-2;
            }
            if(metal[target.row][target.col]!=-1){
                metal[target.row][target.col]=-2;
            }

        }

        void LeeRoute(){
            ofstream f;
            f.open("o1.txt");
            bool path,valid=0;

            int count=0,invalid=0;
            vector<usitype> netList;
            vector<usitype>::iterator it;
            netList.resize(1,0);
            for(int i=0;i<cellList.size();i++){
                for(int j=0;j<4;j++){
                    it=find(netList.begin(),netList.end(),cellList[i].netNum[j]);
                    if(cellList[i].cellID==cellList[i].terminal[j]->cellID){
                        //if(cellList[i])
                    }
                    if(cellList[i].netNum[j]!=*it){
                        //cout<<"Net:"<<cellList[i].netNum[j]<<endl;
                        netList.push_back(cellList[i].netNum[j]);
                        findST(i,j,metal1,metal2,freeGrid);
                        f<<"FreeGrid:"<<endl;
                        for(int i=0;i<freeGrid.size();i++){
                            for(int j=0;j<freeGrid[i].size();j++){
                                f<<freeGrid[i][j]<<" ";
                            }
                            f<<endl;
                        }
                        //findST(i,j,metal2);
                        f<<"NET:"<<cellList[i].netNum[j]<<endl;
                        if(validateST(metal1,metal2,source,target)){
                            path=label(source,target,metal1,metal2,freeGrid,posStack1);
                            //cout<<"path:"<<path<<endl;
                            //Printing!!!!
                                f<<"Metal1_label:"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal1.size();i++){
                                    for(int j=0;j<metal1[i].size();j++){
                                        f<<metal1[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                                f<<"Metal2_label"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal2.size();i++){
                                    for(int j=0;j<metal2[i].size();j++){
                                        f<<metal2[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                            if(path){

                                retracePath(source,target,metal1,metal2);
                                clearLabels(metal1,source,target);
                                clearLabels(metal2,source,target);
                                count++;

                                //Printing!!!!
                                f<<"Metal1_path:"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal1.size();i++){
                                    for(int j=0;j<metal1[i].size();j++){
                                        f<<metal1[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                                f<<"Metal2_path:"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal2.size();i++){
                                    for(int j=0;j<metal2[i].size();j++){
                                        f<<metal2[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                            }
                            else{
                                cout<<"Net:"<<cellList[i].netNum[j]<<endl;
                            }
                        }
                        else{
                            cout<<"Invalid net:"<<cellList[i].netNum[j]<<endl;
                            invalid++;
                        }
                    }
                }
            }
//            for(int k=0;k<netList.size();k++){
//                cout<<" "<<netList[k];
//            }
//            cout<<endl;
            cout<<"total netts:"<<netList.size()-1<<endl;
            cout<<"invalid:"<<invalid<<endl;
            cout<<"Routed:"<<count<<endl;
            cout<<"Not Routed due to obstacles:"<<netList.size()-1-invalid-count<<endl;
            //cout<<expMetal1.size()<<endl;
            for(int i=0;i<expMetal1.size();i++){
                //cout<<"in1: ";
                for(int j=0;j<expMetal1[i].size();j++){
                    //cout<<" in2";
                    f<<expMetal1[i][j]<<" ";
                }
                f<<endl;
            }

        f.close();
        }
};


/****************************FUNCTION TO CALCULATE THE CPU TIME***********************************/ //taken from online source
//double getcputime(void){
//
//    struct timeval tim;
//    struct rusage ru;
//
//    getrusage(RUSAGE_SELF, &ru);
//    tim=ru.ru_utime;
//    double t=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
//    tim=ru.ru_stime;
//    t+=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
//
//    return t;
//}


int main(int argc, char*argv[]){

    srand(3895);
    cellGrid cg("one.net");
    cg.createInitPlacement();
    cg.SA();
    cg.fillGrid();
    cg.LeeRoute();

//    double cputime = getcputime();         //get the cpu time for the program and print
//    cout<<"#cputime:"<<cputime<<"s"<<endl;

    //////////To get the memory usage of the program and print--taken from an online source
//    FILE *fp;
//    pid_t pid = getpid();
//    char command[255];
//    char memory[255];
//    sprintf(command,"pmap  %d | grep total | awk '{ print $2 }'", pid);
//    fp = popen(command, "r");
//    fgets(memory, 255, fp);
//    cout<<"#memory usage:"<<memory<<endl;

}
